/*
 * https://leetcode.cn/problems/rotated-digits
 * 数位dp
 */
class Solution {
public:
    // 函数 findIntegers 接受一个整数 n 作为参数，
    // 返回从 0 到 n 之间的所有不含连续 1 的非负整数的个数。
    int findIntegers(int n) {
        // 计算 n 的位数
        int length = 0;
        int nCopy = n;  // 复制 n 以避免修改原始值
        while (nCopy) {  // 循环直到 nCopy 变为 0
            length++;  // 每次循环长度加 1
            nCopy = nCopy >> 1;  // 将 nCopy 右移一位
        }
        
        // 如果 n 是 1 位数，则结果直接为 2（0 和 1）
        if (length == 1)
            return 2;
        
        // 计算 f(n)，其中 f[i] 表示 i 位二进制数中不含连续 1 的个数
        int f[length];
        f[0] = 1;  // 1 位数时只有 0 或 1
        f[1] = 2;  // 2 位数时有 00, 01, 10 （11 不符合条件）
        for (int i = 2; i < length; i++) {
            // 动态规划公式：f[i] = f[i-1] + f[i-2]
            // 当前位为 0 时，可以是前面 i-1 位的所有组合
            // 当前位为 1 时，只能是前面 i-2 位的所有组合（因为不能有两个连续的 1）
            f[i] = f[i - 1] + f[i - 2];
        }
        
        int pointer = length - 1;  // 从最高位开始检查
        int sum = 0;  // 累计符合条件的数
        while (pointer >= 0) {
            // 检查当前位是否为 1
            if (n & (1 << pointer)) {
                // 如果当前位和下一位都是 1，说明找到了连续的 1
                if (n & (1 << (1 + pointer))) {
                    // 在此之后的所有情况都符合要求，所以累加这些情况
                    for (int i = pointer - 1; i >= 0; i -= 2) {
                        sum += f[i];
                    }
                    break;  // 找到连续 1 后跳出循环
                }
                // 如果还没有连续 1，加上当前位置之前的组合数
                sum += f[pointer];
            }
            pointer--;  // 移动到下一位
        }
        
        // 最后，如果 n 本身也是稀疏数（没有连续 1），则加上 n
        return sum + 1;
    }
};
